T - Permutation

制約的に3乗は厳しそう…

出てくる数字が1~N、というのもポイントになりそう。

考察

追加する時にどういう情報があれば嬉しいか？を考える

今から追加する数字が右端よりも大きいか？小さいか？みたいなのは気になるので、右端の値を持っておきたくなる

ここから遷移を考えてみる

…と思ったけど、右端に新しい数字を追加するにしても「どれが残ってるか？」が分からないのできつくなる

残り使えるのは何か？みたいな情報が欲しくなります

もうちょっと状態を同一視できないか

例えば右端が4で"<"が書いてあったとき、手持ちが{2,5,8,10}でも{3,11,22,33}でも残り使える数字は3つ(5,8,10とか11,22,33とか)なので、そこからの遷移は同じ値になる。

つまりここで「右端より大きい/小さい数字がいくつあるか」を状態として持っておくと良さそう、というお気持ちになる

よく考えると、「右端が違うくてもkが同じなら遷移も同じでは？」となる、あと小さい方の個数は「手持ちの数-大きい数字の個数」で求められることも分かる

dp[i][j] // i番目まで考えて、右端より大きいのがj個ある時

結構シンプルになった…？

もっかい遷移を考えます